package leetcode.doublepointer;

import java.util.Arrays;

//844. 比较含退格的字符串
public class BackspaceCompare {

    public static void main(String[] args) {
        String s = "ac#b";
        System.out.println(backspaceCompareP(s, "abb#"));
    }

    //smallMa
    public static boolean backspaceCompare(String s, String t) {

        StringBuilder stringBuffer = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {

            if ("#".equals(s.substring(i, i + 1))) {
                if (stringBuffer.length() != 0) {
                    stringBuffer.deleteCharAt(stringBuffer.length() - 1);
                }

            } else {
                stringBuffer.append(s.substring(i, i + 1));
            }

        }

        StringBuilder stringBuffer2 = new StringBuilder();
        for (int i = 0; i < t.length(); i++) {

            if ("#".equals(t.substring(i, i + 1))) {
                if (stringBuffer2.length() != 0) {
                    stringBuffer2.deleteCharAt(stringBuffer2.length() - 1);
                }

            } else {
                stringBuffer2.append(t.substring(i, i + 1));
            }

        }
        if (stringBuffer.toString().equals(stringBuffer2.toString())) {
            return true;
        } else {
            return false;
        }

    }

    //将上面的方法提取出来
    public static boolean backspaceCompare2(String s, String t) {
        return build(s).equals(build(t));
    }

    private static String build(String s) {
        StringBuffer stringBuffer = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {

            if ("#".equals(s.substring(i, i + 1))) {
                if (stringBuffer.length() != 0) {
                    stringBuffer.deleteCharAt(stringBuffer.length() - 1);
                }

            } else {
                stringBuffer.append(s.substring(i, i + 1));
            }

        }
        return stringBuffer.toString();
    }


    //双指针---一边移动指针 一边做判断比较是否相等
    public static boolean backspaceCompare3(String s, String t) {
        int p = s.length() - 1, q = t.length() - 1;
        int skipS = 0, skipT = 0;
        while (p >= 0 || q >= 0) {
            while (p >= 0) {
                if (s.charAt(p) == '#') {
                    skipS++;
                    p--;
                } else if (skipS > 0) {
                    p--;
                    skipS--;
                } else {
                    break;
                }

            }
            while (q >= 0) {
                if (t.charAt(q) == '#') {
                    skipT++;
                    q--;
                } else if (skipT > 0) {
                    q--;
                    skipT--;
                } else {
                    break;
                }
            }
            if (p >= 0 && q >= 0) {
                if (s.charAt(p) != t.charAt(q)) {
                    return false;
                }
            } else {
                if (q >= 0 || p >= 0) {
                    return false;
                }
            }
            p--;
            q--;
        }

        return true;
    }


    /**
     * 利用快慢指针来模拟栈的过程，来实现将字符删除
     */

    public static boolean backspaceCompare4(String s, String t) {
        return getString(s).equals(getString(t));
    }

    private static String getString(String s) {
        char[] chars = s.toCharArray();
        int slow = 0;
        for (int fast = 0; fast < s.length(); fast++) {
            if ('#' == chars[fast]) {
                if (slow > 0) {
                    slow--;
                }
            } else {
                chars[slow++] = chars[fast];
            }
        }
        //拷贝数组
        char[] res = Arrays.copyOfRange(chars, 0, slow);
        return String.valueOf(res);
    }

    /**
     * 字符串切片，然后比较俩字符串
     * <p>
     * 有多个#的时候会出错
     */
    public static boolean backspaceComparePError(String s, String t) {
        int index = s.indexOf("#");
        String s1 = s.substring(0, index - 1);
        String s2 = s.substring(index + 1);
        String sP = s1 + s2;
        int index2 = t.indexOf("#");
        String t1 = t.substring(0, index2 - 1);
        String t2 = t.substring(index2 + 1);
        String tP = t1 + t2;
        return sP.equals(tP);
    }


    //双指针
    public static boolean backspaceCompareP(String s, String t) {
        int p = s.length() - 1;
        int q = t.length() - 1;
        int sp = 0, tp = 0;
        while (p >= 0 || q >= 0) {
            while (p >= 0) {
                if (s.charAt(p) == '#') {
                    sp++;
                    p--;
                } else if (sp > 0) {
                    p--;
                    sp--;
                } else {
                    break;
                }
            }
            while (q >= 0) {
                if (t.charAt(q) == '#') {
                    tp++;
                    q--;
                } else if (tp > 0) {
                    q--;
                    tp--;
                } else {
                    break;
                }
            }
            if (p >= 0 && q >= 0) {
                if (s.charAt(p) != t.charAt(q)) {
                    return false;
                }
            } else {
                if (q >= 0 || p >= 0) {
                    return false;
                }
            }
            p--;
            q--;
        }
        return true;
    }

    //利用stringBuffer
    public static boolean backspaceCompareP2(String s, String t) {
        return check(s).equals(check(t));
    }

    private static String check(String s) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            if ("#".equals(s.substring(i, i + 1))) {
                if (sb.length() != 0) {
                    //如果等于#，就将sb里的值删除一个,也就是删除最后一个
                    sb.deleteCharAt(sb.length() - 1);
                }

            } else {
                sb.append(s, i, i + 1);
            }

        }
        return sb.toString();
    }
}
